package com.example.demo.LeetCode.number;

public class Fib1 {
    public static int solution(int n ){
      if (n < 2){
          return n;
      }
      int dp[] = {0,1};
      // 0 1 1 2 3 5 8 13 21 34 55
      for (int i = 2 ; i <= n ; i++){
          // dp[n] = dp[n-1] + dp[n-2]
          // dp[n+1] = dp[n] + dp[n-1]
          //         = dp[n-1] + dp[n-2] + dp[n-1]
         int sum = dp[1] + dp[0];
         dp[0] = dp[1];
         dp[1] = sum;
      }
      return  dp[1];
    }


    public static void main(String[] args) {
        int ans = solution(4);
        System.out.println(ans);
    }

}
